package com.mxw.算法之美.a10堆;

/**
 * @author Administrator
 * @create 2024/7/30 16:40
 */
public class a01Heap {

    /**
     * 堆: 完全二叉树, 每个节点的值都大于或小于其子节点的值
     * <p>
     * 堆化：新插入的节点与父节点对比大小，不满足的进行交换。删除的时候，需要把第二大的元素放到堆顶
     */

    // 建堆
    public static void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapify(a, n, i);
        }
    }

    private static void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            // 左节点
            if (i * 2 <= n && a[i] < a[i * 2]) {
                maxPos= i * 2;
            }
            // 右节点
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i){
                break;
            }
            swap(a,i,maxPos);
            i=maxPos;
        }
    }

    private static void swap(int[] a, int n, int i) {

    }

    public static int[] heap = new int[10];

    public static int count = 0;

    public void insert(int data) {
        // 堆满了
        if (heap.length >= count) {
            return;
        }

        count++;
        heap[count] = data;
        int i = count;
        // i/2 父节点
        while (i / 2 > 0 && heap[i] > heap[i / 2]) {
            // 自下往上堆化，交换父节点
            int temp = heap[i];
            heap[i] = heap[i / 2];
            heap[i / 2] = temp;
            i = i / 2;
        }
    }
}
